package 简单.数学;

/**
 * 给你一个整数 n ，表示比赛中的队伍数。比赛遵循一种独特的赛制：
 * <p>
 * 如果当前队伍数是 偶数 ，那么每支队伍都会与另一支队伍配对。
 * 总共进行 n / 2 场比赛，且产生 n / 2 支队伍进入下一轮。
 * 如果当前队伍数为 奇数 ，那么将会随机轮空并晋级一支队伍，
 * 其余的队伍配对。总共进行 (n - 1) / 2 场比赛，且产生 (n - 1) / 2 + 1 支队伍进入下一轮。
 * 返回在比赛中进行的配对次数，直到决出获胜队伍为止。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/count-of-matches-in-tournament
 */
public class 比赛中的配对次数_1688 {

    public static void main(String[] args) {

        System.out.println(numberOfMatches(7));

    }

    /**
     * 模拟
     *
     * @param n
     * @return
     */
    public static int numberOfMatches(int n) {
        int ans = 0;
        while (n > 1) {
            if (n % 2 == 1) {  //奇数时有一个队伍直接晋级
                ans++;
            }
            n = n / 2;
            ans += n;
        }
        return ans;
    }

    /**
     * 数学
     * 可以看成换酒问题
     * 每次配对都会减少1个队伍，相当于每2个空瓶，换1瓶红酒，每次换算都会减少2-1个瓶子
     * 注意边界问题，假设开局有3个队伍，当剩下1个队伍时不能进行匹配，那么可以匹配的队伍是n-1个
     *
     * @param n
     * @return
     */
    public static int efficientNumberOfMatches(int n) {
        return n - 1;
    }

}
